package com.fang.algorithm.zuo.tree;

import java.util.PriorityQueue;

/**
 * @author lingxiao.fang
 * @Desc 二叉树中第K小的元素
 * @createTime 2025/3/9 16:15
 */
public class Test06_KthSmallestTree {
    private static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        System.out.println(kthSmallest(root, 1));
    }

    private static int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        PriorityQueue<TreeNode> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        inOrder(root, priorityQueue);
        int ans = -1;
        int index = 1;
        while (!priorityQueue.isEmpty()) {
            TreeNode node = priorityQueue.poll();
            if (index == k) {
                ans = node.val;
                break;
            }
            index++;
        }
        return ans;
    }

    private static void inOrder(TreeNode root, PriorityQueue<TreeNode> priorityQueue) {
        if (root == null) {
            return;
        }
        inOrder(root.left, priorityQueue);
        priorityQueue.add(root);
        inOrder(root.right, priorityQueue);
    }
}
